package array.binarySearch;

/**
 * 题目: 给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
        完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
        不能使用任何内置的库函数，如  sqrt 。
 */

public class perfectSquare {
    public boolean isPerfectSquare(int num) {
        if (num == 0) return true; // 0 是完美平方数

        int left = 1; // 从1开始，避免mid=0
        int right = num;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 关键：使用除法避免溢出和除以零
            int quotient = num / mid;

            if (mid < quotient) {
                left = mid + 1;
            } else if (mid > quotient) {
                right = mid - 1;
            } else {
                // 当 mid == num/mid 时，检查是否完全匹配
                return (mid * mid == num);
            }
        }
        return false;
    }
}